




/*
C语言实现图的数据结构。
图有下面几种表示方法：邻接矩阵，邻接表，十字链表，多重链表。

邻接矩阵，在稠密连接的图中比较有优势。
邻接表：计算出度比较方便，计算入度比较麻烦。（如果是带权值的图，比较麻烦，必须建立一个边的结构体）
十字链表：描述有向图，方便计算出入度，边可以带权值。描述无向图的话，边重复，占用的内存会增加两倍，不建议用它描述无向图。
多重链表：十字链表的简化版，描述无向图。
*/

// 有限状态机可以看作是带权值的有向图，因此这里用十字链表来描述图。



#include"stl_graph.h"
			   		   

//   
#include<math.h>
#include"stl_.h" //
#include"gl_.h" //辅助画图

// 绘制图
void draw_graph(Graph* graph)
{
	int vcount = graph->vertex_list.count; // 顶点数量

	int description_r = 50;   // 描述区域的半径。
	int r = description_r / sinf(PI / vcount / 1.5);  //  -description_r;   
	r -= description_r;

	graphics_fill_area(0, 0, GraphicsDevice_width, GraphicsDevice_height, RGB_lightgray);
	int cx = GraphicsDevice_width / 2, cy = GraphicsDevice_height / 2;  // 绘图中心。
	ListNode* cursor = graph->vertex_list.tail;
	for (int i = 0; i < vcount; i++) {
		cursor = cursor->next;
		int ddx = (r + description_r) * cosf(2 * PI * i / vcount);
		int ddy = (r + description_r) * sinf(2 * PI * i / vcount);
		draw_circle(cx + ddx, cy + ddy, description_r, RGB_black);
		int w = 1.414 * description_r;
		draw_rectangle(cx + ddx - w / 2, cy + ddy - w / 2, w, w, RGB_green);


		int v = ((Vertex*)cursor->datap)->value;
		v = v % 100;
		char str[4] = "    ";	str[0] = v / 10 + '0';	str[1] = v % 10 + '0';
		((Vertex*)cursor->datap)->sign = i; // 后面绘图要用这个来索引位置。

		//在中心绘制文本： 文本是ascii格式
		int str_dw = TextFont_defaul.size;
		int str_dh = TextFont_defaul.size;
		draw_string_no_frame(cx + ddx - str_dw / 2, cy + ddy - str_dh / 2, str, 2, TextFont_defaul);

	}

	// 下面绘制箭头  

	int tail, head; // 箭头索引。
	//float delta_angle = 2 * PI / vcount / 5;
	float delta_angle = 0;
	printfs(" \r\n  \r\n ");
	ListNode* vex_cursor = graph->vertex_list.tail;
	for (int i = 0; i < graph->vertex_list.count; i++) {

		vex_cursor = vex_cursor->next;
		printfs(" \r\n  vex:%f   outArc.count = %d  : ",
			((Vertex*)vex_cursor->datap)->value,
			((Vertex*)vex_cursor->datap)->outArc.count);

		ListNode* arc_cursor = ((Vertex*)vex_cursor->datap)->outArc.tail;
		for (int j = 0; j < ((Vertex*)vex_cursor->datap)->outArc.count; j++) {
			arc_cursor = arc_cursor->next;
			int h = ((Arc*)arc_cursor->datap)->headvex->value;
			printfs(" head:%d  ", h);

			// 绘制箭头
			head = ((Arc*)arc_cursor->datap)->headvex->sign;
			tail = ((Arc*)arc_cursor->datap)->tailvex->sign;

			int sx = cx + (r + description_r) * cosf(2 * PI * tail / vcount + delta_angle);
			int sy = cy + (r + description_r) * sinf(2 * PI * tail / vcount + delta_angle);
			int ex = cx + (r + description_r) * cosf(2 * PI * head / vcount - delta_angle);
			int ey = cy + (r + description_r) * sinf(2 * PI * head / vcount - delta_angle);
			int dx = ex - sx;
			int dy = ey - sy;
			float len = sqrtf(dx * dx + dy * dy);
			sx += TextFont_defaul.size * 1.5 * dx / len;
			sy += TextFont_defaul.size * 1.5 * dy / len;
			ex -= TextFont_defaul.size * 1.5 * dx / len;
			ey -= TextFont_defaul.size * 1.5 * dy / len;

			draw_arrow(sx, sy, ex, ey, RGB_black);

		}
	}


	//	GD_wait_key_input();

}
// 打印图
void print_graph(Graph* graph)
{
	int vcount = graph->vertex_list.count; // 顶点数量

	printfs(" \r\n print graph::::  vex count = %d ", vcount);

	ListNode* vex_cursor = graph->vertex_list.tail;
	for (int i = 0; i < graph->vertex_list.count; i++) {

		vex_cursor = vex_cursor->next;
		printfs(" \r\n  vex:%f   outArc.count = %d  : ",
			((Vertex*)vex_cursor->datap)->value,
			((Vertex*)vex_cursor->datap)->outArc.count);

		ListNode* arc_cursor = ((Vertex*)vex_cursor->datap)->outArc.tail;
		for (int j = 0; j < ((Vertex*)vex_cursor->datap)->outArc.count; j++) {
			arc_cursor = arc_cursor->next;
			printfs(" head:%f  ", ((Arc*)arc_cursor->datap)->headvex->value);
		}

		arc_cursor = ((Vertex*)vex_cursor->datap)->inArc.tail;
		for (int j = 0; j < ((Vertex*)vex_cursor->datap)->inArc.count; j++) {
			arc_cursor = arc_cursor->next;
			printfs(" tail:%f  ", ((Arc*)arc_cursor->datap)->tailvex->value);
		}

	}

	//	GD_wait_key_input();

}



/// <summary>
/// 寻找图中顶点值对应的顶点。
/// </summary>
/// <param name="graph">图</param>
/// <param name="vex_data">顶点的值</param>
/// <returns>顶点指针</returns>
Vertex* Graph_find_vertex(Graph* graph, float vex_data)
{
	ListNode* list_cursor;
	list_cursor = graph->vertex_list.tail->next;
	for (int i = 0; i < graph->vertex_list.count; i++) {
		if (vex_data == ((Vertex*)list_cursor->datap)->value) return list_cursor->datap;
		list_cursor = list_cursor->next;
	}
	return NULL;
}

/// <summary>
/// 图中插入一条边，如果是有向图，边的方向是 尾 ---->> 头
/// </summary>
/// <param name="graph">图</param>
/// <param name="arc">边结构体</param>
/// <param name="tailvertex">尾节点</param>
/// <param name="headvertex">头节点</param>
void Graph_ins_arc(Graph* graph, Arc* arc, Vertex* tailvertex, Vertex* headvertex)
{
	list_push_front(&graph->arc_list, arc);
	arc->arc_list_node = graph->arc_list.tail->next;
	arc->tailvex = tailvertex;
	arc->headvex = headvertex;
	

	list_push_front(&headvertex->inArc, arc);
	arc->inArcNode = headvertex->inArc.tail->next;
	list_push_front(&tailvertex->outArc, arc);
	arc->outArcNode = tailvertex->outArc.tail->next;
}


/// <summary>
/// 插入顶点，新插入的顶点没有边。
/// </summary>
/// <param name="graph">图</param>
/// <param name="vertex">顶点</param>
void Graph_ins_vertex(Graph* graph, Vertex* vertex)
{
	list_push_front(&graph->vertex_list, vertex);
	list_init(&vertex->inArc, NULL);
	list_init(&vertex->outArc, NULL);
	vertex->vex_list_node = graph->vertex_list.tail->next;
}

/// <summary>
/// 移除边，移除边会找到边的头尾节点，分别删除两个节点的入边和出边。
/// </summary>
/// <param name="graph">图</param>
/// <param name="arc">边</param>
void Graph_remove_arc(Graph* graph, Arc* arc)
{
	// 重点警告：这里单链表的remove函数，会破坏outArcNode，inArcNode与弧节点的对应关系！
	// 因此删除弧节点不能直接调用remove！否则会出错。 
	// 因此这里手动实现链表节点的删除
	List* list = &arc->tailvex->outArc;
	ListNode* node = arc->outArcNode;
	{
		ListNode* n = node->next;
		node->datap = n->datap;
		if (n == list->tail) {
			list->tail = node;  // 检查是否需要跟新尾节点
		}
		node->next = n->next;
		{
			// 节点要更新了，要修改data里的指针。
			Arc* node_arc = (Arc*)node->datap;  
			node_arc->outArcNode = node;
		}	
		ListNode_deallocate(n);
		list->count--;
	//	if (list->count == 0) list->tail = NULL;
	}

	list = &arc->headvex->inArc;
	node = arc->inArcNode;
	{
		ListNode* n = node->next;
		node->datap = n->datap;
		if (n == list->tail) {
			list->tail = node;  // 检查是否需要跟新尾节点
		}
		node->next = n->next;
		{
			// 节点要更新了，要修改data里的指针。
			Arc* node_arc = (Arc*)node->datap;
			node_arc->inArcNode = node;
		}
		ListNode_deallocate(n);
		list->count--;
		//	if (list->count == 0) list->tail = NULL;
	}

	// 移除边表
//	list_remove(&graph->arc_list, arc->arc_list_node);
	list = &graph->arc_list;
	node = arc->arc_list_node;
	{
		ListNode* n = node->next;
		node->datap = n->datap;
		if (n == list->tail) {
			list->tail = node;  // 检查是否需要跟新尾节点
		}
		node->next = n->next;
		{
			// 节点要更新了，要修改data里的指针。
			Arc* node_arc = (Arc*)node->datap;
			node_arc->arc_list_node = node;
		}
		ListNode_deallocate(n);
		list->count--;
		//	if (list->count == 0) list->tail = NULL;
	}


	// 下面是错误用法。
	//list_remove(&arc->tailvex->outArc, arc->outArcNode);
	//list_remove(&arc->headvex->inArc, arc->inArcNode);
}

/// <summary>
/// 移除顶点，移除顶点会移除与该顶点相关的边
/// </summary>
/// <param name="graph">图</param>
/// <param name="vertex">顶点</param>
void Graph_remove_vertex(Graph* graph, Vertex* vertex)
{
	int count;
	ListNode* cursor;
	cursor = vertex->inArc.tail;
	count = vertex->inArc.count;
	for (int i = 0; i < count; i++) {
		// 删除 入边 出节点 对应的出边。
		Graph_remove_arc(graph, (Arc*)(cursor->datap));
		cursor = cursor->next;
	}

	cursor = vertex->outArc.tail;
	count = vertex->outArc.count;
	for (int i = 0; i < count; i++) {
		// 删除 出边 入节点 对应的入边。
		Graph_remove_arc(graph, (Arc*)(cursor->datap));
		cursor = cursor->next;
	}

	// 移除边表
	//list_remove(&graph->vertex_list, vertex->vex_list_node);
	List* list = &graph->vertex_list;
	ListNode* node = vertex->vex_list_node;
	{
		ListNode* n = node->next;
		node->datap = n->datap;
		if (n == list->tail) {
			list->tail = node;  // 检查是否需要跟新尾节点
		}
		node->next = n->next;
		{
			// 节点要更新了，要修改data里的指针。
			Vertex* node_vex = (Vertex*)node->datap;
			node_vex->vex_list_node = node;
		}
		ListNode_deallocate(n);
		list->count--;
		//	if (list->count == 0) list->tail = NULL;
	}
}

/// <summary>
/// 初始化图
/// </summary>
/// <param name="graph">图</param>
/// <param name="is_directed_graph">是否有向图</param>
void Graph_init(Graph* graph, bool is_directed_graph)
{
	list_init(&graph->vertex_list, NULL);
	list_init(&graph->arc_list, NULL);
	graph->is_directed_graph = is_directed_graph;
}

/// <summary>
/// 销毁图，会删除所有顶点和边
/// </summary>
/// <param name="graph">图</param>
void Graph_destroy(Graph* graph)
{
	ListNode* node = graph->vertex_list.tail;
	int count = graph->vertex_list.count;
	for (int i = 0; i < count; i++) {
		Graph_remove_vertex(graph, (Vertex*)(node->datap));
		node = node->next;
	}
//	list_destroy(&graph->arc_list);
//	list_destroy(&graph->vertex_list);

}
//

//////////////  下面是图的算法，两个最小生成树算法，两个最短路径算法（现实一个） /////////////////////////////////////////////////


int arc_compare(Arc* arc1, Arc* arc2) {
	if (arc1->value > arc2->value)return 1;
	else if (arc1->value < arc2->value)return -1;
	else return 0;
}

/// <summary>
/// Kruskal算法实现最小生成树。
/// 这个函数会将图看作是无向图
/// </summary>
/// <param name="graph">图</param>
/// <param name="min_tree">这个链表要空的（函数里会初始化），链表的datap是 Arc的指针，根据边的描述可以确定一个图</param>
void Graph_MinTree_Kruskal(Graph* graph, List* min_tree) {
	
	// 这个图必须是无向图。如果是有向图，得先变成无向图再开始生成最小树。
	// if (graph->is_directed_graph)graph->is_directed_graph = false;

	// 首先，对边的值构建最小堆，并且将所有顶点的sign定义序号，然后依次寻找最小边，直到所有顶点都被包含。
	Heap heap;
	Heap_allocate(&heap, graph->arc_list.count + 1, false, arc_compare);
	Heap_build_with_list(&heap, &graph->arc_list);
	list_init(min_tree, NULL);
	ListNode* listnode = graph->vertex_list.tail;
	for (int i = 0; i < graph->vertex_list.count; i++) {
		listnode = listnode->next;
		((Vertex*)listnode->datap)->sign = i;  // 顶点的sign值作为并查集
	}
	// 初始化并查集。
	Union u;
	int vcount = graph->vertex_list.count;
	union_allocate(&u, vcount);
	union_init(&u);
	// 遍历边。
	for (Datapointer dp = Heap_pop(&heap); dp != NULL; dp = Heap_pop(&heap)) {
		int s1 =  union_find_root(&u, ((Arc*)dp)->headvex->sign);
		int s2 =  union_find_root(&u, ((Arc*)dp)->tailvex->sign);
		//printfs("  \r\n  sign: %d , %d data: %d , %d  root : %d , %d  ",
		//	((Arc*)dp)->headvex->sign, ((Arc*)dp)->tailvex->sign,
		//	(int)((Arc*)dp)->headvex->value, (int)((Arc*)dp)->tailvex->value, s1, s2);

		if (s1 != s2) {  // 边的两个节点不属于同一个集合
			list_push_back(min_tree, dp);
			int union_count = union_union(&u, s1, s2);
#if(0)// 打印图的链表
			{
				printfs("\r\n arc count : %d ", min_tree->count);
				ListNode* node = min_tree->tail;
				for (int i = 0; i < min_tree->count; i++) {
					node = node->next;
					Arc* arc = node->datap;
					printfs("\r\n arc value: %d , head: %d  , tail: %d ",
						(int)(arc->value), (int)arc->headvex->value, (int)arc->tailvex->value);
				}
				printfs("\r\n");
				GD_wait_key_input();
			}
#endif

			if (union_count >= vcount)break;  // 合并后集合的点数已经满足要求了，推出循环。
		}
	}

	union_deallocate(&u);
	Heap_deallocate(&heap);
}


// 边，顶点都保存到链表里，遍历图直接在链表里遍历就行了，没必要进行深度优先或者广度优先遍历，反正都不确定……


#include<float.h>  // 这里定义了浮点数的最大最小值等常量

#include"sl_matrix.h"
//#define NO_Adjacent  9999 // 边的权重大于这个值，表示不相邻
/// <summary>
/// Dijkstra算法实现最短路径。这里要保证边的权值都是正的。
/// 如果边有负权值，可能会得不到正确的路径。
/// 最短路径的算法，用邻接矩阵来计算效率比较高，如果用邻接表，算法太复杂。
/// </summary>
/// <param name="m">图的临界矩阵，data[i][j] 表示i节点到j节点的边的权值，值大于9999表示不连通</param>
/// <param name="path">path.data[i]表示从源点到顶点i之间最短路径的前驱结点</param>
/// <param name="dist">dist.data[i]表示从源点到顶点i的最短路径长度</param>
/// <param name="start_index">源点的索引</param>
/// <returns></returns>
int Graph_mat_MinWay_Dijkstra(mat m, ivec path, vec dist, int start_index)
{
	if (m.cols == m.rows && m.cols == path.size && m.cols == dist.size &&
		start_index >= 0 && start_index < dist.size) {

		int count = m.cols;
		ivec final;   // 标记各顶点的最短路径是否找到。=0是未找到，V集合。=1是已找到，S集合。
		ivec_allocate(&final, count);
		// 初始化
		for (int i = 0; i < count; i++) {
			dist.data[i] = m.data[start_index][i];
			final.data[i] = 0;
			path.data[i] = start_index;  // 更新dist，就要更新path
		}
		final.data[start_index] = 1;

		// V - S集合任找一点，即找一个final == 0 的点。

		//每次循环会标记一个顶点u，直到所有顶点被标记（循环次数就是顶点数-1，起点已找到最短路径0）
		for (int k = 1; k < count; k++) {
			float min = NO_Adjacent * 2;
			int u = 0;
			//找到当前未被标记的距离起点最近的顶点u
			for (int i = 0; i < count; i++) {
				if (dist.data[i] < min && final.data[i] == 0) {
					u = i;
					min = dist.data[i];
				}
			}
			final.data[u] = 1;//标记顶点u
			/* 遍历顶点u的邻结点，当 dist[u] + arcs[u][j] < dist[j]时
			（顶点u距离起点s的长度dist[u]加上顶点u与邻接点j的距离arcs[u][j]小于顶点j距离起点s的距离dist[j]），
			更新顶点j距离起点的路径长度 */
			for (int j = 0; j < count; j++) {
				if (final.data[j] == 0 && dist.data[u] + m.data[u][j] < dist.data[j]) {
					dist.data[j] = dist.data[u] + m.data[u][j];
					path.data[j] = u;
				}
			}
		}

		ivec_deallocate(&final);
	}
	return 1;
}

/// <summary>
/// 拓扑排序
/// </summary>
/// <param name="graph">有向图</param>
/// <param name="topo">这个链表要空的（函数里会初始化）。datap是顶点指针，输出拓扑排序的顶点顺序（不唯一）</param>
/// <returns>如果有回路，拓扑排序失败</returns>
bool Graph_TopoSort(Graph* graph, List *topo)
{
	List list;
	list_init(topo, NULL);
	list_init(&list, NULL);
	int count = graph->vertex_list.count;
	ListNode* node = graph->vertex_list.tail;
	for (int i = 0; i < count; i++) {
		node = node->next;
		// sign 记录入度
		((Vertex*)node->datap)->sign = ((Vertex*)node->datap)->inArc.count;
		if (((Vertex*)node->datap)->sign == 0) {
			list_push_back(&list, node->datap);
		}
	}
	while (list.count)
	{
		Vertex* v = list_head(&list);
		//Vertex* v2;
		list_pop_front(&list);
		list_push_back(topo, v);
		node = v->outArc.tail;
		for (int i = 0; i < v->outArc.count; i++) {  // 将节点v所指的顶点入度减一，如果入度减为零，则推入list链表。
			node = node->next;
			((Arc*)node->datap)->headvex->sign--;
			if (((Arc*)node->datap)->headvex->sign == 0) {
				list_push_back(&list, ((Arc*)node->datap)->headvex);
			}
		}
	}

	if (topo->count < count) return false;  // 排序失败，图中有回路
	else  return true; // 排序成功。

}
//

//////////////      /////////////////////////////////////////////////////////////////////////////////////////////////

// 下面测试图。 图的可视化，通过绘制图比较方便看。

#include"mcu_.h"
char str[1024];

// 最多一百条边。或一百个顶点
float arc_data[100][3]; //每条边的数据是： 尾节点值，头节点值，边的值。
int arc_num;
float vex_data[100];  // 顶点数据。
int vex_num = 0;

bool is_data_in_array(float* array, int array_len, float data) {
	for (int i = 0; i < array_len; i++) {
		if (data == array[i])return true;
	}
	return false;
}

// 返回：is_directed
bool  init_graph_data(char* str,int len)
{
	bool is_directed = false; 
	char* p = str;
	if (str_match("W", str)) {
		is_directed = false;
		while (*p != '\n') p++;
		p++;   // 匹配到下一行
	}
	else
	{
		is_directed = true;
	}

	//下面提取数据：
	arc_num = 0;
	vex_num = 0;
	int cursor = 0;
	for (int i = 0; i < 100; i++) {
		int m;
		m = str_to_float(p, &arc_data[i][0]); 
		if (m > 0)
		{		
			if (is_data_in_array(vex_data, vex_num, arc_data[i][0])==false)  // 检查是否新节点。
			{
				vex_data[vex_num] = arc_data[i][0];
				vex_num++;
			}
			p += m;
		}
		else
		{
			return is_directed;
		}

		m = str_to_float(p, &arc_data[i][1]);
		if (m > 0)
		{
			if (is_data_in_array(vex_data, vex_num, arc_data[i][1])==false)  // 检查是否新节点。
			{
				vex_data[vex_num] = arc_data[i][1];
				vex_num++;
			}
			// 新边
			arc_num++;
			p += m;
		}
		else
		{
			return is_directed;
		}

		m = str_to_float(p, &arc_data[i][2]);
		if (m <= 0)  // 边默认的权值是1.
		{
			arc_data[i][2] = 1;
		}
		while (*p != '\n') {
			p++;
			if (*p == 0)return is_directed;
		}
		p++;   // 匹配到下一行

	}
	return is_directed;
}

char line_str[128];

void test_ui_graph()
{
	int id = 1;
	int id0 = 0;
	while (true)
	{
		Vertex vex[100];
		Arc arc[100];
		printfs(" node remain : %d ", ListNode_remain());

		Graph graph;
		mcu_delay_ms(500);
		
		int len = get_graph_string(str, 1024);
		id = len;
	//	printfs("%s", str);
		bool is_directed = init_graph_data(str, len);
		Graph_init(&graph, is_directed);

		// 先打印数据
#if(0)
		printfs(" vex num : %d ", vex_num);
		for (int i = 0; i < vex_num; i++) {
			printfs(" \r\n %d ", (int)vex_data[i]);
		}
		printfs("\r\n arc num : %d ", arc_num);
		for (int i = 0; i < arc_num; i++) {
			printfs(" \r\n %d >> %d   %d ",
				(int)arc_data[i][0], (int)arc_data[i][1], (int)arc_data[i][2]);
		}
#endif

		//下面开始建立图，
		for (int i = 0; i < vex_num; i++) {
			id += (vex_data[i] * i);
			vex[i].value = vex_data[i];
		//	printfs(" \r\n   vex data = %f ",  vex[i].value);
			Graph_ins_vertex(&graph, &vex[i]);
		}
		// 连接规则：
		for (int i = 0; i < arc_num; i++) {
			id += (arc_data[i][2] * i);

			arc[i].value = arc_data[i][2];
			Vertex* vh, * vt;
			vt = Graph_find_vertex(&graph, arc_data[i][0]);
			vh = Graph_find_vertex(&graph, arc_data[i][1]);

			Graph_ins_arc(&graph, &arc[i], vt, vh);

		//	printfs(" \r\n %d >> %d   %d   ||  %f  >> %f ",(int)arc_data[i][0], (int)arc_data[i][1], (int)arc_data[i][2] ,vt->value,vh->value );
		//	draw_graph(&graph);
		//	GD_wait_key_input();
		}

		id = len;

		//if (id0 != id) 
		{  // 图有变化，重新打印图
			id0 = id;
			id = 0;
			print_graph(&graph);
			//	printfs(" node remain : %d ", ListNode_remain());
			draw_graph(&graph);
		}
		printfs(" \r\n finish     %d  \r\n", id);
		Graph_destroy(&graph);
	}


}

// 现在插入边，绘制图都测试通过。
void test_dgraph()
{


	Vertex vex[20];
	Arc arc[30];

	Graph graph;
	Graph_init(&graph,true);

	int vex_num = 13;
	int arc_num = vex_num * 1.5;

	for (int i = 0; i < vex_num; i++) {
		vex[i].value = i;		
		printfs(" \r\n   vex[%d] data = %f ", i, vex[i].value);
		Graph_ins_vertex(&graph, &vex[i]);
	}

	// 连接规则：
	for (int i = 0; i < arc_num; i++) {
		arc[i].value = i + 50;

		if (i < vex_num - 1) {
			Graph_ins_arc(&graph, &arc[i], &vex[i], &vex[i + 1]);
		}
		else
		{
			Graph_ins_arc(&graph, &arc[i], &vex[i - vex_num + vex_num / 3], &vex[i - vex_num + 1]);
		}
	//	print_graph(&graph);

		draw_graph(&graph);
	}

	print_graph(&graph);
	draw_graph(&graph);

}


//测试最小生成树
void test_graph_min_tree()
{
	// graph -无向图最小生成树例子 408 2025数据结构 P241，图6.15
	char str[] =
		"1 3 1 \n 1 4 5 \n 1 2 6 \n 2 3 5 \n 3 5 6 \n 3 4 5 \n 6 3 4 \n 6 4 2 \n 6 5 6 \n 5 2 3  ";

	Vertex vex[100];
	Arc arc[100];
	printfs(" node remain : %d ", ListNode_remain());

	Graph graph;

	int len = sizeof(str);
	//	printfs("%s", str);
	bool is_directed = init_graph_data(str, len);
	Graph_init(&graph, is_directed);

	// 先打印数据
#if(0)
	printfs(" vex num : %d ", vex_num);
	for (int i = 0; i < vex_num; i++) {
		printfs(" \r\n %d ", (int)vex_data[i]);
	}
	printfs("\r\n arc num : %d ", arc_num);
	for (int i = 0; i < arc_num; i++) {
		printfs(" \r\n %d >> %d   %d ",
			(int)arc_data[i][0], (int)arc_data[i][1], (int)arc_data[i][2]);
	}
#endif
	//下面开始建立图，
	for (int i = 0; i < vex_num; i++) {
		vex[i].value = vex_data[i];
		//	printfs(" \r\n   vex data = %f ",  vex[i].value);
		Graph_ins_vertex(&graph, &vex[i]);
	}
	// 连接规则：
	for (int i = 0; i < arc_num; i++) {
		arc[i].value = arc_data[i][2];
		Vertex* vh, * vt;
		vt = Graph_find_vertex(&graph, arc_data[i][0]);
		vh = Graph_find_vertex(&graph, arc_data[i][1]);

		Graph_ins_arc(&graph, &arc[i], vt, vh);

		//	printfs(" \r\n %d >> %d   %d   ||  %f  >> %f ",(int)arc_data[i][0], (int)arc_data[i][1], (int)arc_data[i][2] ,vt->value,vh->value );
		//	draw_graph(&graph);
		//	GD_wait_key_input();
	}

	// 打印图
	print_graph(&graph);
	//	printfs(" node remain : %d ", ListNode_remain());
	draw_graph(&graph);

	GD_wait_key_input();
	List list;
	Graph_MinTree_Kruskal(&graph, &list);

	printfs("\r\n arc count : %d ", list.count);
	ListNode* node = list.tail;
	for (int i = 0; i < list.count; i++) {
		node = node->next;
		Arc* arc = node->datap;
		printfs("\r\n arc value: %d , head: %d  , tail: %d ",
			(int)(arc->value), (int)arc->headvex->value, (int)arc->tailvex->value);
	}
	printfs("\r\n");


	printfs(" \r\n finish   \r\n    \r\n");

	GD_wait_key_input();



	Graph_destroy(&graph);


}

// 测试最短路径，Dijkstra 算法
void test_graph_dij()
{
	mat m;
	vec dist;
	ivec path;
	mat_allocate(&m, 5, 5);
	ivec_allocate(&path, 5);
	vec_allocate(&dist, 5);

	int arc[5][5] = {
		{0,10,10000,10000,5},
		// {10000,10000,10000,10000,10000},
		 {10000,0,1,10000,2},
		{10000,10000,0,4,10000},
		{7,10000,6,0,10000},
		{10000,3,9,2,0} };

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			m.data[i][j] = arc[i][j];
		}
	}
	Graph_mat_MinWay_Dijkstra(m, path, dist, 2);

	mat_print(m);
	vec_print(dist);
	ivec_print(path);

//	GD_wait_key_input();

	mat_deallocate(&m);
	ivec_deallocate(&path);
	vec_deallocate(&dist);
}


void test_topo()
{
	// graph -无向图最小生成树例子 408 2025数据结构 P241，图6.15
	char str[] =
		"1 4  \n 4 5 \n 3 5 \n 1 2 \n 2 3 \n 2 4  ";

	Vertex vex[100];
	Arc arc[100];
	printfs(" node remain : %d ", ListNode_remain());

	Graph graph;

	int len = sizeof(str);
	//	printfs("%s", str);
	bool is_directed = init_graph_data(str, len);
	Graph_init(&graph, is_directed);


	//下面开始建立图，
	for (int i = 0; i < vex_num; i++) {
		vex[i].value = vex_data[i];
		//	printfs(" \r\n   vex data = %f ",  vex[i].value);
		Graph_ins_vertex(&graph, &vex[i]);
	}
	// 连接规则：
	for (int i = 0; i < arc_num; i++) {
		arc[i].value = arc_data[i][2];
		Vertex* vh, * vt;
		vt = Graph_find_vertex(&graph, arc_data[i][0]);
		vh = Graph_find_vertex(&graph, arc_data[i][1]);

		Graph_ins_arc(&graph, &arc[i], vt, vh);

		//	printfs(" \r\n %d >> %d   %d   ||  %f  >> %f ",(int)arc_data[i][0], (int)arc_data[i][1], (int)arc_data[i][2] ,vt->value,vh->value );
		//	draw_graph(&graph);
		//	GD_wait_key_input();
	}

	// 打印图
	print_graph(&graph);
	//	printfs(" node remain : %d ", ListNode_remain());
	draw_graph(&graph);

	GD_wait_key_input();

	List list;
	Graph_TopoSort(&graph, &list);

	ListNode* node = list.tail;
	printfs("  \r\n topo ::");
	for (int i = 0; i < list.count; i++) {
		node = node->next;
		printfs("  %f  ", ((Vertex*)node->datap)->value);
	}


	printfs(" \r\n finish   \r\n    \r\n");

	GD_wait_key_input();



	Graph_destroy(&graph);




}
